// 题目描述
// 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
// 如果存在，返回 true ；否则，返回 false 。叶子节点是指没有子节点的节点。

// 题目链接：https://leetcode.cn/problems/path-sum
// 文章链接：https://blog.csdn.net/ITSOK_123/article/details/125005811

// 深度优先（O(N),O(N)）
class Solution {
public:
    void findPath(TreeNode* root,int num,int target,bool &falg){
        // 新加入了节点更新路径和
        num += root->val;
        // 到达叶子节点
        if(root->left == nullptr && root->right == nullptr){
            // 满足求解条件，结果标志为真
            if(num == target){
                falg = true;
            }   
            // 否则继续递归
            return;
        }
        // 左子树递归
        if(root->left)  findPath(root->left,num,target,falg);
        // 右子树递归
        if(root->right) findPath(root->right,num,target,falg);
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        // 根节点为空，返回false
        if(root == nullptr) return false;
        // falg用来标记求解结果
        bool falg = false;
        findPath(root,0,targetSum,falg);
        return falg;
    }
};


// 广度优先（O(N),O(N)）

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        // 空树直接返回false
        if(root == nullptr) return false;
        // 初始化广度遍历的树节点队列
        queue<TreeNode*> que;
        queue<int> num;
        que.push(root);
        num.push(root->val);
        // 队列不为空则节点未处理完
        while(!que.empty()){
            // 取出树节点队列以及路径和队列的首元素
            TreeNode* node = que.front();
            int res=num.front();
            que.pop();
            num.pop();
            // 如果到了叶子节点而且路径和满足要求则直接跳出遍历，返回true
            if(node->left==nullptr && node->right==nullptr && res==targetSum)
                return true;
            if(node->left){
                que.push(node->left);
                // 下一层节点入队，并将其对应的节点路径和存储
                num.push(node->left->val + res);
            }  
            if(node->right){
                que.push(node->right);
                // 下一层节点入队，并将其对应的节点路径和存储
                num.push(node->right->val + res);
            }  
        }
        // 节点处理完仍然没有找到加和为targetSum的路径，返回false
        return false;
    }
};

// 递归解决（O(N),O(H)）

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr) return false;
        // 是叶节点，判断路径和是否等于目标和
        if(root->left == nullptr && root->right == nullptr){
            return root->val == targetSum;
        }
        // 注意这里的targetSum更新为减去当前父节点值之后的值
        // 这使得可以方便递归
        return(hasPathSum(root->left,targetSum-root->val) ||
            hasPathSum(root->right,targetSum-root->val));
    }
};

